|
|
In article <Xns### [at] 204213191226>, "Rafal 'Raf256' Maj"
<raf### [at] raf256com> wrote:
>> Photons are stored in a kd-tree and radiosity data is stored in an
>> oct-tree.
>
> What's the difference beetwen them ? In shortcut, if You can explain
> please.
From an data structure perspective an oct-tree is a special case of an
unbalanced three dimensional kd-tree (3d-tree). The oct-tree in POV-Ray is
consequently implemented as a linked structure. The kd-tree used by photons
uses an array as storage and is balanced.
>> Unless this is an extremly simplified example, this looks very much
>> like a binary tree to me. Both, kd-trees and oct-trees, are fairly
>> advanced data structures compared to simple binary trees.
>
> I was quesing that for 1d surfaces we use bin-tress, and for 2d-surfaces
> simmilar structure, but each parent have 4 childs. And for 3 directions - 8
> childs.
That is the basic concept, but it isn't all that simple.
Essentially, a kd-tree does not have to separate space in a symmetric manner
while an oct-tree does exactly that. One major difference for the
implementation is the already noted design decision of using an array or a
linked structure. There are space and efficiency tradeoffs.
And example of an oct-tree:
<http://www.npac.syr.edu/copywrite/pcw/node279.html>
An example of a two dimensional kd-tree (a 2d-tree):
<http://www-hpcc.astro.washington.edu/faculty/marios/papers/perform/node3.ht
ml>
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|